package a.codetop.归并;

public class 归并_合有序数组 {

    //常用 合有序数组
    private int[] mergeOrderNums(int[] L, int[] R) {
        int[] res = new int[L.length + R.length];
        int l=0,r=0, n1=L.length, n2=R.length;
        int i=0;
        while(l<n1 && r<n2){
            if(L[l] <= R[r]) res[i++] = L[l++];
            else res[i++] = R[r++];

        }
        if(l==n1){
            for (int j =r; j<n2 ; j++) res[i++] = R[j];
        }else if(r==n2){
            for (int j = l; j < n1; j++) res[i++] = L[j];
        }
        return res;
    }

    // 归并排序
    public int[] merge_sort(int[] nums, int l, int r){ // [闭区间]
        if(l==r){
            return new int[]{nums[l]};
        }

        int lt = l, rt = r;
        int m = l + (r-l)/2;
        int[] L = merge_sort(nums, lt, m);
        int[] R = merge_sort(nums, m + 1, rt);
        return mergeOrderNums(L, R);
    }
}
